/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-10-20
 * Time:20:11
 */

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //递归算法
//    List<Integer> list=new ArrayList<>();
//    public List<Integer> preorderTraversal(TreeNode root) {
//        if(root==null){
//            return list;
//        }
//        list.add(root.val);
//        preorderTraversal(root.left);
//        preorderTraversal(root.right);
//        return list;
//    }
    //最好的写法
//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> list=new ArrayList<>();
//        if(root==null){
//            return list;
//        }
//        list.add(root.val);
//        List<Integer> leftRoot=preorderTraversal(root.left);
//        list.addAll(leftRoot);
//        List<Integer> rightRoot=preorderTraversal(root.right);
//        list.addAll(rightRoot);
//        return list;
//    }

    //}

}
public class TreeNode {
     int val;
     TreeNode left;
      TreeNode right;
      TreeNode() {

      }
      TreeNode(int val) {
          this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }

}